package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/4/2 10:18
 * @DESCRIPTION
 */
// 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
// 并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
public class DeleteNode {
    // 思路一：迭代法
    public TreeNode method1(TreeNode root, int key) {
        TreeNode node = root;//node用于遍历节点，找到要删除的节点
        TreeNode father = new TreeNode();//father 用于记录被遍历节点的父节点，用于重构二叉树
        int flag = 0;//判断要删除是根节点，还是父节点的左子树或者右子树 0为根节点 1为左子树 2为右子树
        // 迭代找到要删除的节点
        while (node != null) {
            if (node.val > key) {
                father = node;
                node = node.left;
                flag = 1;
            } else if (node.val < key) {
                father = node;
                node = node.right;
                flag = 2;
            } else {
                break;
            }
        }
        //要删除的节点可能不存在二叉树中  直接返回即可
        if (node == null) {
            return root;
        }

        if (node.right == null && node.left == null) { // 该节点如果是叶子节点则直接删除
            if (flag == 0) {
                return null;
            } else if (flag == 1) {
                father.left = null;
            } else {
                father.right = null;
            }
        } else if (node.right != null && node.left == null) {// 该节点只有右子树
            if (flag == 0) {
                root = root.right;
            } else if (flag == 1) {
                father.left = node.right;
            } else {
                father.right = node.right;
            }
        } else if (node.right == null && node.left != null) {// 该节点只有左子树
            if (flag == 0) {
                root = root.left;
            } else if (flag == 1) {
                father.left = node.left;
            } else {
                father.right = node.left;
            }
        } else {// 该节点有左、右子树
            if (flag == 0) {
                return method1Aux(root);
            } else if (flag == 1) {
                TreeNode temp = method1Aux(node);
                father.left = temp;
            } else {
                TreeNode temp = method1Aux(node);
                father.right = temp;
            }
        }
        return root;
    }
    //该函数处理了 根节点为要删除的节点，且根节点有左子树和右子树
    //返回新的根节点
    public TreeNode method1Aux(TreeNode root) {
        //将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左子节点的左孩子节点位置上，返回删除节点右孩子为新的根节点。
        TreeNode res = root.right;
        TreeNode node = res;
        while (node.left != null) {
            node = node.left;
        }
        node.left = root.left;
        return res;
    }

    //该方法是 代码随想录 中的迭代法
    public TreeNode method2(TreeNode root, int key) {
        if (root == null){
            return null;
        }
        //寻找对应的对应的前面的节点，以及他的前一个节点
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null){
            if (cur.val < key){
                pre = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                pre = cur;
                cur = cur.left;
            }else {
                break;
            }
        }
        //代表要删除的节点是该树的根节点
        if (pre == null){
            return deleteOneNode(cur);
        }
        //这里在判断pre的哪个孩子节点是要删除的节点
        if (pre.left !=null && pre.left.val == key){
            pre.left = deleteOneNode(cur);
        }
        if (pre.right !=null && pre.right.val == key){
            pre.right = deleteOneNode(cur);
        }
        return root;
    }

    public TreeNode deleteOneNode(TreeNode node){
        //这个判空感觉没有必要--通过力扣测试--没有这个判空也是能通过的，不知道存在的意义是什么
        if (node == null){
            return null;
        }
        //这里将五种情况 用右子树是否为空 分成2种情况来处理
        if (node.right == null){//右子树为空
            return node.left;
        }
        //右子树不为空
        TreeNode cur = node.right;
        while (cur.left !=null){
            cur = cur.left;
        }
        cur.left = node.left;
        return node.right;
    }

    //该方法是 代码随想录 中的递归法
    public TreeNode method3(TreeNode root, int key) {
        if (root == null) return root;
        if (root.val == key) {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }
        //如果是要删除的节点，则返回处理好后的节点，让父节点连接该新节点
        //如果不是要删除的节点，返回自身，左子树右子树其实相当于没有变化
        if (root.val > key) root.left = method3(root.left, key);
        if (root.val < key) root.right = method3(root.right, key);
        return root;
    }
}
